package Aleehot100;

import java.util.Arrays;

/**
 * ClassName: c099
 * Package: Aleehot100
 * Description:31. 下一个排列
 *
 * @Author BCXJ
 * @Create 2025/9/16 07:55
 * @Version 1.0
 * @Since 1.0
 */
public class c099 {
    public static void main(String[] args) {
        int[] arr = {1,2,5,4,2};
        nextPermutation(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        // 找出下降的第一个位置 i
        int i = n - 2;
        while(i >= 0 && nums[i] >= nums[i + 1]) {
            i --;
        }
        // 找出比 i大的元素第一个元素j(范围限制在 i + 1 ~  n - 1)
        if(i >= 0) { // i存在才进入，如果i = -1，即说明情况是 3, 2, 1
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }

            // 交换i 和 j （此时 i + 1 ~ n -1 仍然是有序的）
            swap(nums, i, j);
        }
        // 倒置有序的部分
        reverse(nums, i + 1, n - 1);
    }

    private static void reverse(int[] nums, int i, int j) {
        while(i < j) {
            swap(nums, i, j);
            i ++;
            j --;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        if(i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

}
